package code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 * @leetcode 3sum,4sum=Target
 * 问题描述：给定一个数组，求所有的a+b+c=target，4sum同理，转为3sum问题
 * 问题分解：
 * 先将数组中的元素排序，然后
 * 先固定一个参数a，那么问题变成了求b+c=x的问题，
 * min......max
 * min+max=sum,如果sum>0,那么需要将max的值变小（向左移动一个数），否则，
 * 需要将min的值，调大（即向右移动一个数）
 * 这样既可找到固定a的时候，是否存在b、c的所有解（遇到相同的元素的时候要过滤）
 * 
 * 由多个参数变量来共同决定所求的解
 * 一个参数的时候，很好搞。直接hash
 * 这种调节参数的大小的思想，其实也广泛使用在其他的实验领域。
 * 两个参数的时候，可大，可小。这样就可以对当前的结果进行调节，使得所有解越来越接近目标值.
 */
public class Code15 {
	
	
    public List<List<Integer>> threeSum(int[] num) {
    	List<List<Integer>> result=new ArrayList<List<Integer>>();
    	Arrays.sort(num);
    	int i,j,k;
    	int n=num.length;
    	for(i=0;i<n-2;i++){
    	    if(i>0 && num[i]==num[i-1])
    	        continue;
    		j=i+1;
    		k=n-1;
    		int sum=num[i]+num[j]+num[k];
    		while(j<k){
    			sum=num[i]+num[j]+num[k];
    			if(sum==0)
    			{
    				List<Integer> list=new ArrayList<Integer>();
    				list.add(num[i]);
    				list.add(num[j]);
    				list.add(num[k]);
    				result.add(list);
    				//重复的元素，过滤掉
    				while(k>0 && num[k-1]==num[k])
    					k--;
    				k--;
    			}
    			else if(sum>0){
    				//重复的元素，过滤掉
    				while(k>0 && num[k-1]==num[k])
    					k--;
    				k--;
    			}
    			else{
    				while(j<n-1 && num[j+1]==num[j])
    					j++;
    				j++;
    			}
    		}
    	}
    	return result;
    }
    public int threeSumClosest(int[] nums, int target) {
        int ans=Integer.MAX_VALUE;
        int closest=Integer.MAX_VALUE;
    	Arrays.sort(nums);
    	int i,j,k;
    	int n=nums.length;
    	for(i=0;i<n-2;i++){
    	    if(i>0 && nums[i]==nums[i-1])
    	        continue;
    		j=i+1;
    		k=n-1;
    		while(j<k){
    			int sum=nums[i]+nums[j]+nums[k]-target;
    			if(closest>Math.abs(sum)){
    				ans=nums[i]+nums[j]+nums[k];
    				closest=Math.abs(sum);
    			}
    			if(closest==0)
    				return target;
    			if(sum>0){
    				//重复的元素，过滤掉
    				while(k>0 && nums[k-1]==nums[k])
    					k--;
    				k--;
    			}
    			else{
    				while(j<n-1 && nums[j+1]==nums[j])
    					j++;
    				j++;
    			}
    		}
    	}
    	return ans;
    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
    	List<List<Integer>> result=new ArrayList<List<Integer>>();
    	Arrays.sort(nums);
    	int i,j,k,l;
    	int n=nums.length;
    	
    	for(i=0;i<n-3;i++){
    	    if(i>0 && nums[i]==nums[i-1])
    	        continue;
    	    /*
    	     * 枚举第一个元素i
    	     */
    	    for(j=i+1;j<n-2;j++){
		    	/*
		    	 * 枚举第二个元素j
		    	 */
    	    	if(j-1>i && nums[j]==nums[j-1])
    	    		continue;
	    		k=j+1;
	    		l=n-1;
	    		while(k<l){
	    			int sum=nums[i]+nums[j]+nums[k]+nums[l]-target;
	    			if(sum==0)
	    			{
	    				List<Integer> list=new ArrayList<Integer>();
	    				list.add(nums[i]);
	    				list.add(nums[j]);
	    				list.add(nums[k]);
	    				list.add(nums[l]);
	    				result.add(list);
	    				//重复的元素，过滤掉
	    				while(l>0 && nums[l-1]==nums[l])
	    					l--;
	    				l--;
	    			}
	    			else if(sum>0){
	    				//重复的元素，过滤掉
	    				while(l>0 && nums[l-1]==nums[l])
	    					l--;
	    				l--;
	    			}
	    			else{
	    				while(k<n-1 && nums[k+1]==nums[k])
	    					k++;
	    				k++;
	    			}
	    		}
    	    }
    	}
    	return result;
    }
    
    public static void main(String[] args){
    	int[] nums={1,0,-1,0,-2,2};
    	int[] num={0,0,0,0};
    	System.out.println(new Code15().fourSum(num, 0));
    }
}
